/*
 * @lc app=leetcode.cn id=4 lang=typescript
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lc code=start
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  const findK = (nums1: number[], i: number, nums2: number[], j: number, k: number): number => {
    // num1空了，直接返回num2第k小的元素
    if (i >= nums1.length) return nums2[j + k - 1];
    //  num2空了，直接返回num1第k小的元素
    if (j >= nums2.length) return nums1[i + k - 1];
    // 返回最小的那个
    if (k === 1) return Math.min(nums1[i], nums2[j]);

    // 将k二分
    const half = k >> 1;

    // 计算中间值
    let mid1 = i + half - 1 < nums1.length ? nums1[i + half - 1] : Number.POSITIVE_INFINITY;
    let mid2 = j + half - 1 < nums2.length ? nums2[j + half - 1] : Number.POSITIVE_INFINITY;

    if (mid1 < mid2) {
      // 缩小nums1的区间
      return findK(nums1, i + half, nums2, j, k - half);
    }
    // 缩小num2的范围
    return findK(nums1, i, nums2, j + half, k - half);
  };

  const n = nums1.length + nums2.length;
  const x = findK(nums1, 0, nums2, 0, (n + 1) >> 1);
  if ((n & 1) === 1) {
    return x;
  } else {
    const y = findK(nums1, 0, nums2, 0, ((n + 1) >> 1) + 1);
    return (x + y) / 2;
  }
}
// @lc code=end
